/**
 * LeetCode 9. 回文数
 */
public class Solution_9 {
    /**
     * 方法二：反转一半数字
     * <p>
     * 反转全部数字可能会发生溢出，所以只反转一半数字
     * <p>
     * 当原数字小于或等于反转后的数字时，标志着已经反转了一半
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 空间复杂度：O(1)
     */
    public boolean isPalindrome(int x) {
        // 负数必不是回文；除 0 以外，以 0 结尾的数字也不是回文
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int reversedNum = 0;
        while (x > reversedNum) {
            reversedNum = reversedNum * 10 + x % 10;
            x /= 10;
        }
        // 如果原数字长度为偶数，那么反转一半时，x == reversedNum
        // 如果原数字长度为奇数，那么反转一半时，reversedNum 比 x 多一位
        return x == reversedNum || x == (reversedNum / 10);
    }

    /**
     * 方法一：转为字符串
     */
    public boolean isPalindrome1(int x) {
        // 负数必不是回文；除 0 以外，以 0 结尾的数字也不是回文
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        String str = Integer.toString(x);
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
